Logica formale - Sommario

Richiami di logica formale, focus sulle proposizioni, sui connettivi e sulle congiunzioni. Sommario integrato con appunti sui predicati, quantificatori. Appunti presi tra il 25-26/09


La logica formale matematica è la branca della matematica che permette di dare un linguaggio rigoroso e formale alla nostra materia: essa è utile per evitare ambiguità e darci, appunto, un linguaggio chiaro e definito.

Proposizioni

Breve descrizione di cos'è una proposizione...


Proposizione

Una proposizione è una parte del discorso, ovvero un'affermazione, a cui si associa un valore di verità o falsità
ESEMPI

  • q: Guillame è più alto di 1,80m -> V
  • r: Rome è la capitale della Francia -> F
  • r: Domani pioverà -> ? => NON è ammissibile come proposizione, in quanto non si può dire con certezza; invece con la teoria della probabilità si può assegnare un valore da 0 a 1.
    Per dare un nome a una proposizione si usano le lettere
    Invece per i valori di verità o falsità essi sono o

Connettivi
Connettivi

Connettivi: cosa sono, quali useremo...


Connettivi

Il connettivo, nella logica formale, viene usato per comporre una nuova Proposizioni partendo da quelle già esistenti.
Un connettivo viene caratterizzato da una tabella di verità, che descrive ogni valore di ogni proposizione.
Studieremo i seguenti connettivi: la Negazione, la Congiunzione, la Disgiunzione, l'^implicazione e la ^doppiaimplicazione

Negazione

^negazione
La negazione è l'unico connettivo unario (che prende SOLO una proposizione) di cui studieremo.
Viene indicata con , e viene letta come "non q"
La sua tavola della verità è la seguente:

Congiunzione

^congiunzione
La congiunzione tra due proposizioni viene indicata con e si legge come "p e q"
La tavola della verità associata è la seguente:

V V V
V F F
F V F
F F F

Disgiunzione

^disgiunzione
La disgiunzione di due proposizioni viene indicata con e si legge come "p oppure q". Tuttavia, nella lingua italiana vi è un'ambiguità nell'uso della congiunzione "o": può avere due significati diversi, che sono quella esclusiva (in latino aut) e quella inclusiva (in latino vel).
Nella matematica si preferisce usare per indicare la disgiunzione vel, ma esiste anche per indicare quella aut.
La tavola della verità di è la seguente.

V V V
V F V
F V V
F F F

Osservazione 1.

Quando due tabelle della verità, associate ad una proposizione l'una, danno gli stessi valori della verità, si dice che queste proposizioni sono equivalenti.
ESEMPIO 1. Ricavare le tavole della verità di e di .
Si ricava la tavola della prima proposizione, ovvero .

V V V F
V F F V
F V F V
F F F V

Ora l'altra tavola. ()

V V F F F
V F F V V
F V V F V
F F V V V

Si nota che e ci danno i stessi valori, pertanto . (Leggi di De Morgan)
Lo stesso discorso vale per .


Tautologia
Tautologia

Tautologia: cos'è, alcuni esempi. Dimostrazione-esempio di una delle tautologie


Una tautologia è una proposizione composta che è sempre vera, indipendentemente dai valori delle proposizioni.
Eccovi alcuni esempi.

  • : tertium non datur
  • : non contraddictio
  • : modus ponens
  • : modus tollens
  • : reductio ad absurdum

DIMOSTRAZIONE (EX. 5)

  1. Si osserva che è sempre falsa: di conseguenza si può riscriverla come , per indicare che è una proposizione sempre falsa, indipendentemente dai valori .
  2. Si osservano le seguenti per :
    1. Per la legge di De Morgan,
    2. Per la definizione dell'implicazione in Connettivi,
    3. Pertanto
  3. Secondo le osservazioni appena svolte, si deduce che
  4. Inoltre, osservando che ,
  5. Usando di nuovo la definizione dell'implicazione,
  6. Osservando che , si conclude che
  7. Pertanto
Predicati e Quantificatori
Predicati e Quantificatori

Definizione generale dei predicati corredata con degli esempi, breve focus sui quantificatori, negazione dei predicati con quantificatori


Definizioni generali

DEF 1. Si definisce il predicato come la parte del linguaggio che contiene delle variabili. Esempi di seguito per illustrare il concetto del predicato.

ES 1. Sia definisce il predicato èù
Se è Pietro, allora si legge come "Lo studente Pietro è più alto di 1,7m."
In questo caso si ha un predicato unario, nel senso che accetta solo una variabile, ovvero .

ES 2. Sia è.
Se è Pietro e è Francesca, allora si legge come "Lo studente Pietro è amico della studentessa Francesca".
In questo caso si ha un predicato binario; continuando così si può definire anche dei predicati -ari.

ES 3. Sia .

DEF 2. Si definisce il quantificatore come l'espressione che, nel nostro linguaggio, corrisponde a "esiste" oppure "tutti".
Essi sono i seguenti.

OSSERVAZIONE 1. Un modo per trasformare i predicati in una Proposizione è di utilizzare i quantificatori appena definiti.

ES. 1.1. si legge come "Ogni studente è più alto di 1,7m"
Si nota che, mediante il quantificatore, il predicato è una proposizione; si definisce in questo caso come variabile muta.

Ora si può comporre frasi come la seguente.
che si legge come "Tutti sono amici di "; dopodiché si può anche comporre un'altra fase, comeche si legge come "Esiste una studentessa di cui tutti sono amici"

ES 1.2. Per comporre la frase "In ogni ospedale c'è un medico che ha sbagliato tutte le diagnosi" si usa la seguente:

\forall x, \mathcal{Q}(x,y)) \neq \forall x, \exists y: \mathcal{Q}(x,y$$

Negazione dei predicati con i quantificatori

OSSERVAZIONE 1. Si prende in esame il seguente. èùche si legge come "Tutti i studenti sono più alti di 1,7m"
Pensando col procedimento linguistico, la negazione di questa frase verrebbe come "Esiste almeno un studente meno alto o uguale a 1,7m".
Pertanto,

OSSERVAZIONE 2. Da quanto detto si deduce che NON è necessariamente equivalente a , in quanto ci vuole solo un ente per rendere falsa.

Analogamente, lo stesso discorso vale per REGOLA GENERALE Da qui si evince la regola generale per negare un predicato con i quantificatori;

  1. I quantificatori esistenziali devono essere scambiati con quelli opposti; nel senso che da il quantificatore esistenziale si trasforma nel quantificatore universale , viceversa per .
  2. Si nega il predicato .

ES 1. Riprendendo l'esempio 2 da Definizioni generali, se si vuole dire che "Non è vero che esiste una studentessa che è amica di tutti", si esegue così:
ES 2. Riprendendo l'esempio 3 da Definizioni generali, per dire che "Non è vero che in ogni ospedale c'è un medico che ha sbagliato tutte le diagnosi" si fa il seguente: ES. 3 Richiamandoci alla definizione del limite, rigorosamente definito dal matematico Cauchy nel suo scritto Cours d'analyse (1821), ovvero èSe si vuole negare che esiste il limite in , allora ciò significa, dal punto di vista matematico, il seguente.